package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2101. 引爆最多的炸弹
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/24 9:07
 */
public class MaximumDetonation {

    public static void main(String[] args) {
        MaximumDetonation test = new MaximumDetonation();

        // 2
//        int[][] bombs = {{2,1,3},{6,1,4}};

        // 1
//        int[][] bombs = {{1, 1, 5}, {10, 10, 5}};

        // 5
        int[][] bombs = {{1,2,3},{2,3,1},{3,4,2},{4,5,3},{5,6,4}};

        int i = test.maximumDetonation(bombs);
        System.out.println(i);
    }

    private Map<Integer, List<Integer>> map = new HashMap<>();
    private Set<Integer> set = new HashSet<>();
    private int max;
    private int item;

    public int maximumDetonation(int[][] bombs) {
        int length = bombs.length;
        for (int i = 0; i < length; i++) {
            int[] bombi = bombs[i];
            long xi = bombi[0];
            long yi = bombi[1];
            long ri = bombi[2];
            for (int j = i + 1; j < length; j++) {
                int[] bombj = bombs[j];
                long xj = bombj[0];
                long yj = bombj[1];
                long rj = bombj[2];
                long s = (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj);
                if (s <= ri * ri) {
                    map.computeIfAbsent(i, v -> new ArrayList<>()).add(j);
                }
                if (s <= rj * rj) {
                    map.computeIfAbsent(j, v -> new ArrayList<>()).add(i);
                }
            }
        }
        for (int i = 0; i < length; i++) {
            set.clear();
            item = 0;
            find(i);
        }
        return max;
    }

    private void find(int key) {
        List<Integer> list = map.get(key);
        item++;
        set.add(key);
        max = Math.max(max, item);
        if (list == null) {
            return;
        }
        for (int v : list) {
            if (set.contains(v)) {
                continue;
            }
            find(v);
        }
    }

}
